/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */
#include "bmsn-routing.h"
#include "bmsn-generator.h"
#include "bmsn-topology.h"
#include "bmsn-path-selector-tag.h"
#include "routing-tools.h"
#include "ns3/queue.h"
#include "ns3/pointer.h"
#include "ns3/uinteger.h"
#include "ns3/ipv4-address.h"
#include "ns3/point-to-point-net-device.h"
#include <ostream>
#include <list>
#include <vector>

namespace ns3 {
namespace eecityu {

using namespace ns3;

NS_LOG_COMPONENT_DEFINE ("BmsnRouting");
NS_OBJECT_ENSURE_REGISTERED (BmsnRouting);


/** 
 * \todo Include m_version number and m_version checking functions
 */
TypeId 
BmsnRouting::GetTypeId (void)
{
  static TypeId tid = TypeId ("ns3::eecityu::BmsnRouting")
    .SetParent<Ipv4RoutingProtocol> ()
    .AddConstructor<BmsnRouting> ()
    .AddAttribute ("EnableDeflection",
                   "Set to true if deflection is enabled during routing.",
                   BooleanValue(false),
                   MakeBooleanAccessor (&BmsnRouting::m_enableDeflection),
                   MakeBooleanChecker ())
    .AddAttribute ("EnableRandomness",
                   "Set to true to introduce randomness when routing a packet among multiple paths.",
                   BooleanValue(true),
                   MakeBooleanAccessor (&BmsnRouting::m_enableRandRouting),
                   MakeBooleanChecker ())
    .AddAttribute ("Priority",
                   "The priority of the BMSN routing protocol. Can be a negative value.",
                   IntegerValue(DEFAULT_BMSN_ROUTING_PRI),
                   MakeIntegerAccessor (&BmsnRouting::m_priority),
                   MakeIntegerChecker<int16_t> ())
    // The default value for the x- and y-corrdinates are an impossible
    // value as the valid range for them is [0, DEFAULT_N_ROWS). This
    // invalid default values force them to be initialized when attaching
    // this BmsnRouting protocol object to a node.
    .AddAttribute ("x",
                   "The x coordinate of the node the current BmsnRouting protocol object is attaching.",
                   UintegerValue(DEFAULT_N_ROWS),
                   MakeUintegerAccessor (&BmsnRouting::m_xLocation),
                   MakeUintegerChecker<uint32_t> ())
    .AddAttribute ("y",
                   "The y coordinate of the node the current BmsnRouting protocol object is attaching.",
                   UintegerValue(DEFAULT_N_ROWS),
                   MakeUintegerAccessor (&BmsnRouting::m_yLocation),
                   MakeUintegerChecker<uint32_t> ())
    .AddAttribute ("nRows",
                   "The number of rows of the BMSN topology.",
                   // The default number is an impossible value, such that
                   // an error will occur if this value is forgotten to
                   // be initialized
                   UintegerValue(0),
                   MakeUintegerAccessor (&BmsnRouting::m_nRows),
                   MakeUintegerChecker<uint32_t> ())
    ;

  return tid;
}

BmsnRouting::BmsnRouting(void)
{
  NS_LOG_FUNCTION_NOARGS ();
}

uint32_t 
BmsnRouting::GetXLocation () const
{
  return m_xLocation;
}

uint32_t 
BmsnRouting::GetYLocation () const
{
  return m_yLocation;
}

uint32_t 
BmsnRouting::GetNRows () const
{
  return m_nRows;
}

//bool
//BmsnRouting::RequestRoute (
//  uint32_t interface,
//  Ipv4Header const &ipHeader,
//  Ptr<Packet> packet,
//  RouteReplyCallback routeReply)
//{
//  NS_LOG_FUNCTION (this << interface << &ipHeader << packet << &routeReply);
//
//  NS_LOG_LOGIC ("source = " << ipHeader.GetSource ());
//
//  NS_LOG_LOGIC ("destination = " << ipHeader.GetDestination ());
//
//  if (ipHeader.GetDestination ().IsMulticast ())
//    {
//      NS_LOG_LOGIC ("Multicast destination - returning false");
//      return false; // Let other routing protocols try to handle this
//    }
//
//// This is a unicast packet.  Check to see if we have a route for it.
////
//  NS_LOG_LOGIC ("Unicast destination - looking up");
//  Ipv4Route *route = LookupBmsnRoute (ipHeader.GetDestination (), packet);
//  if (route != 0)
//    {
//      routeReply (true, *route, packet, ipHeader);
//      return true;
//    }
//  else
//    {
//      return false; // Let other routing protocols try to handle this
//                    // route request.
//    }
//}
//
//bool
//BmsnRouting::RequestInterface (Ipv4Address destination, uint32_t& interface)
//{
//  NS_LOG_FUNCTION (this << destination << &interface);
////
//// First, see if this is a multicast packet we have a route for.  If we
//// have a route, then send the packet down each of the specified interfaces.
////
//  if (destination.IsMulticast ())
//    {
//      NS_LOG_LOGIC ("Multicast destination - returning false");
//      return false; // Let other routing protocols try to handle this
//    }
////
//// See if this is a unicast packet we have a route for.
////
//  NS_LOG_LOGIC ("Unicast destination - looking up");
//  // pass a null pointer for the Ptr<Packet> argument
//  Ipv4Route *route = LookupBmsnRoute (destination, 0);
//  if (route)
//    {
//      interface = route->GetInterface ();
//      return true;
//    }
//  else
//    {
//      return false;
//    }
//}

#if 0 // =1 if Ipv4Header object is tobe converted into BmsnHeader object
      // =0 if the default Ipv4Header object is to be used throughout this methods
Ptr<Ipv4Route> 
BmsnRouting::RouteOutput (const Ipv4Header &_header, uint32_t oif, Socket::SocketErrno &sockerr)
{  
  // create a BmsnHeader from the Ipv4Header
  BmsnHeader header (*reinterpret_cast<const BmsnHeader*>(&_header));
  NS_LOG_FUNCTION (this << (Ipv4Header) header << oif);
  NS_LOG_LOGIC ("BmsnTag value = " << header.GetBmsnPathSelectorTag ().GetTagValue ());
  // read the destination address from the IPv4 header
  Ipv4Address destination = header.GetDestination ();

#else
Ptr<Ipv4Route> 
BmsnRouting::RouteOutput (Ptr<Packet> p, const Ipv4Header &header, Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)
{  
  NS_LOG_FUNCTION (this << header << oif);
  // read the destination address from the IPv4 header
  Ipv4Address destination = header.GetDestination ();
#endif
  
  // Multicast goes here
  if (destination.IsMulticast ())
    {
      // Note:  Multicast routes for outbound packets are stored in the
      // normal unicast table.  An implication of this is that it is not
      // possible to source multicast datagrams on multiple interfaces.
      // This is a well-known property of sockets implementation on 
      // many Unix variants.
      // So, we just log it and fall through to LookupStatic ()
      NS_LOG_LOGIC ("RouteOutput()::Multicast destination");
    }
  Ptr<Ipv4Route> rtentry = 
#if 1 // Set to 0 then packets' source address are the loopback address
      // of the orginating nodes
      // Set to 1 then this RouteInput () always return 'no route found'
      // and let the next routing protocol, if configured, to handle
    LookupBmsnRoute (destination, p, 0);
#else
    m_localRoute;
#endif
  NS_LOG_LOGIC ("Route found = " << rtentry);
  if (rtentry)
    { 
      sockerr = Socket::ERROR_NOTERROR;
    }
  else
    { 
      sockerr = Socket::ERROR_NOROUTETOHOST;
    }
  return rtentry;
}

// XXX this method not robust enough to work independent of ListRouting
bool 
BmsnRouting::RouteInput  (Ptr<const Packet> _p, const Ipv4Header &ipHeader, Ptr<const NetDevice> idev,
                             UnicastForwardCallback ucb, MulticastForwardCallback mcb,
                             LocalDeliverCallback lcb, ErrorCallback ecb)
{
  Ptr<Packet> p = _p->Copy ();
  NS_LOG_FUNCTION (this << p << ipHeader << ipHeader.GetSource () << ipHeader.GetDestination () << idev);
  //Ptr<Ipv4> ipv4 = m_node->GetObject<Ipv4> ();

  NS_ASSERT_MSG (!ipHeader.GetDestination ().IsMulticast (), "Multicast routing not supported.");
  //if (ipHeader.GetDestination ().IsMulticast ())
  //  {
  //    NS_LOG_LOGIC ("Multicast destination");
  //    Ptr<Ipv4MulticastRoute> mrtentry =  LookupStatic(ipHeader.GetSource (),
  //      ipHeader.GetDestination (), ipv4->GetInterfaceForDevice (idev));

  //    if (mrtentry)
  //      {
  //        NS_LOG_LOGIC ("Multicast route found");
  //        mcb (mrtentry, p, ipHeader); // multicast forwarding callback
  //        return true;
  //      }
  //    else
  //      {
  //        NS_LOG_LOGIC ("Multicast route not found");
  //        return false; // Let other routing protocols try to handle this
  //      }
  //  }
//
// This is a unicast packet.  Check to see if we have a route for it.
//

  Ptr<Ipv4Route> rtentry = LookupBmsnRoute (ipHeader.GetDestination (), p, idev);
  if (rtentry != 0)
    {
      NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
      ucb (rtentry, p, ipHeader);  // unicast forwarding callback
      return true;
    }
  else
    {
      NS_LOG_LOGIC ("Did not find unicast destination- returning false");
      return false; // Let other routing protocols try to handle this
    }
}

void 
BmsnRouting::NotifyInterfaceUp (uint32_t i)
{}
void 
BmsnRouting::NotifyInterfaceDown (uint32_t i)
{}
void 
BmsnRouting::NotifyAddAddress (uint32_t interface, Ipv4InterfaceAddress address)
{}
void 
BmsnRouting::NotifyRemoveAddress (uint32_t interface, Ipv4InterfaceAddress address)
{}

void 
BmsnRouting::SetIpv4 (Ptr<Ipv4> ipv4)
{
  NS_LOG_FUNCTION (this << ipv4);
  NS_ASSERT_MSG (m_ipv4 == 0 && ipv4 != 0, "Duplicated call to SetIpv4 () method.");
  m_ipv4 = ipv4;
}

void 
BmsnRouting::SetNode (Ptr<Node> n) 
{
  NS_LOG_FUNCTION (n);
  Ptr<Ipv4> ipv4 = n->GetObject<Ipv4> ();
  //// set a reference to the ipv4 protocol object in this routing protocol
  //SetIpv4 (ipv4);
  NS_LOG_LOGIC ("netdevice0 = " << ipv4->GetAddress (0, 0).GetLocal ());
  NS_LOG_LOGIC ("netdevice1 = " << ipv4->GetAddress (1, 0).GetLocal ());
  NS_LOG_LOGIC ("netdevice2 = " << ipv4->GetAddress (2, 0).GetLocal ());
  NS_LOG_LOGIC ("netdevice3 = " << ipv4->GetAddress (3, 0).GetLocal ());
  NS_LOG_LOGIC ("netdevice4 = " << ipv4->GetAddress (4, 0).GetLocal ());
  NS_ASSERT_MSG (n->GetNDevices () == 5, "Invalid number (" << n->GetNDevices () 
    << ") of net devices for a BMSN node.");
  // Obtain the IP address of any one of the net devices installed on this node
  Ipv4Address addr = GetIpv4AddressFromNetDevice (n->GetDevice (1));
  // Obtain the x-location from the 2nd octet of the IP address
  m_xLocation = GetIpv4AddressAtOctet (addr, 2);
  // Obtain the y-location from the 3rd octet of the IP address
  m_yLocation = GetIpv4AddressAtOctet (addr, 1);
  // Initialize the four routes each of which directs packets to one of
  // the four neighbors of this BMSN node
  InitializeRoutes (n);

  NS_LOG_LOGIC ("BmsnRouting protocol object installed on node (" << 
    m_xLocation << ", " << m_yLocation << ")");
}

void 
BmsnRouting::InitializeRoutes (Ptr<Node> n)
{
  NS_LOG_FUNCTION_NOARGS ();
  // Obtain the Ipv4 protocol object from kthe node
  Ptr<Ipv4> ipv4 = n->GetObject<Ipv4> ();
  NS_ASSERT_MSG (ipv4, "Missing the Ipv4 object with this node. " 
    << "The node may not be installed with the Internet protocol stack.");

  uint32_t netId = 0;
  // Obtain the correct interface number and its direction and create
  // a Ipv4Route correspondingly
  for (uint32_t ifIndex = 1; ifIndex <= 4; ifIndex++)
  {
    Ipv4Address addr = ipv4->GetAddress (ifIndex, 0).GetLocal ();
    NS_LOG_LOGIC ("Interface-" << ifIndex << " IPv4 address = " << addr);
    // Assumed the IPv4 address is class-A and obtain the network number.
    // This is used to check for inconsistance network number among the four
    // IPv4 interfaces
    uint32_t thisNetId = GetIpv4AddressAtOctet (addr, 3);
    NS_LOG_LOGIC ("Network number = " << thisNetId << ".0.0.0");
    NS_ASSERT_MSG (netId == 0 || netId == thisNetId, "The network number (" 
      << thisNetId << ".0.0.0) is not the same as the other interfaces (" 
      << netId << ".0.0.0)");
    // update the netId so that all subsequent network number must be the same
    // as this one
    netId = thisNetId;
    // Obtain the direction information from the 4-th octet of the
    // interface's IP address. As defined in BmsnTopology::IsBmsnTopology (),
    // the 4-th octet can only be 1, 2, 3, or 4 where
    // - 1 = north facing interface,
    // - 2 = east facing interface,
    // - 3 = south facing interface,
    // - 4 = west facing interface.
    uint32_t direction = GetIpv4AddressAtOctet (addr, 0);
    // A route for the direction specified by the 4-th octet can be
    // created with the interface number
    Ipv4Address dest (addr.Get () & 0xff000000);
    Ptr<PointToPointNetDevice> dev = DynamicCast<PointToPointNetDevice> (ipv4->GetNetDevice (ifIndex));
    Ipv4RoutingTableEntry newRoutingTableEntry = 
      Ipv4RoutingTableEntry::CreateNetworkRouteTo (
      dest, Ipv4Mask(0xff000000), GetRemoteAddress (dev), ifIndex
      );
    // Convert an Ipv4RoutingTableEntry object into an Ipv4Route object
    Ptr<Ipv4Route> tempRoute = Create<Ipv4Route> ();
    tempRoute->SetSource (ipv4->GetAddress (newRoutingTableEntry.GetInterface (), 0).GetLocal () );
    tempRoute->SetDestination (dest);
    Ptr<Ipv4Route> newRoute = GetIpv4RouteFrom (newRoutingTableEntry, tempRoute, ipv4);
    switch (direction) 
    {
    case 1: // north facing
      m_northRoute = newRoute;
      NS_LOG_LOGIC ("North route created for IP interface " << addr);
      break;
    case 2: // east facing
      m_eastRoute = newRoute;
      NS_LOG_LOGIC ("East route created for IP interface " << addr);
      break;
    case 3: // south facing
      m_southRoute = newRoute;
      NS_LOG_LOGIC ("South route created for IP interface " << addr);
      break;
    case 4: // west facing
      m_westRoute = newRoute;
      NS_LOG_LOGIC ("West route created for IP interface " << addr);
      break;
    default:
      NS_ASSERT_MSG (false, "The 4-th octet (" 
        << direction << ") of the IP address is an impossible "
        << "number for a BMSN topology!");
    }
  }
  // Create a route to the localhost of the node. This route allows a packet
  // to be cirulated back to the RouteInput () method. As only the RouteInput ()
  // has access to Ptr<Packet>, new packet generated from the node and is waiting
  // for the RouteOutput () needs to be circulated back to RouteInput () in order
  // to implement Tag based routing.
  //
  // GetAddress (0, 0) means the 0-th interface and 0-th IP address
  Ipv4Address addr = ipv4->GetAddress (0, 0).GetLocal ();
  NS_LOG_LOGIC ("Interface-0 IPv4 address = " << addr);
  // A route for the direction specified by the 4-th octet can be
  // created with the interface number
  Ipv4Address dest (addr.Get () & 0xff000000);
  Ipv4RoutingTableEntry newRoutingTableEntry = 
    Ipv4RoutingTableEntry::CreateNetworkRouteTo (
    dest, Ipv4Mask(0xff000000), 0
    );
  // Convert an Ipv4RoutingTableEntry object into an Ipv4Route object
  Ptr<Ipv4Route> tempRoute = Create<Ipv4Route> ();
  tempRoute->SetSource (ipv4->GetAddress (newRoutingTableEntry.GetInterface (), 0).GetLocal () );
  tempRoute->SetDestination (dest);
  m_localRoute = GetIpv4RouteFrom (newRoutingTableEntry, tempRoute, ipv4);
  NS_LOG_LOGIC ("Local route created: " << m_localRoute);
}

Ptr<Ipv4Route>
BmsnRouting::LookupBmsnRoute (Ipv4Address dest, Ptr<Packet> p, Ptr<const NetDevice> idev)
{
  NS_LOG_FUNCTION (dest << p);
  if (m_nRows == 0)
    NS_LOG_ERROR ("The number of BMSN rows (0) is invalid. The m_nRows "
    << "must be initialized before this BMsnRouting protocol can "
    << "function properly.");
  if (m_xLocation >= m_nRows) 
    NS_LOG_ERROR ("The x-coordinate (" << m_xLocation << 
                  ") is invalid. It has to be " <<
                  "initialized when the BmsnRouting protocol " <<
                  "object is first aggregated into a node. " << 
                  "SetNode () may not be called before this " << 
                  "protocol object is aggregated into the node.");
  if (m_yLocation >= m_nRows)
    NS_LOG_ERROR ("The y-coordinate (" << 
                  m_yLocation << ") is invalid. It has to be " <<
                  "initialized when the BmsnRouting protocol " <<
                  "object is first aggregated into a node. " << 
                  "SetNode () may not be called before this " << 
                  "protocol object is aggregated into the node.");
  NS_LOG_LOGIC ("Node location = (" << m_xLocation << ", " << m_yLocation << ")");
  NS_ASSERT (
    (m_nRows > 0) 
    && (m_xLocation < m_nRows) 
    && (m_yLocation < m_nRows)
    );

  // Obtain the x- and y-coordinate of the destination node
  uint32_t xDest = GetIpv4AddressAtOctet (dest, 2);
  uint32_t yDest = GetIpv4AddressAtOctet (dest, 1);
  NS_LOG_LOGIC ("Packet destinating to node (" 
    << xDest << ", " << yDest << ")");
  NS_LOG_LOGIC ("BMSN size = " << m_nRows << "-by-" << m_nRows);
  // Find the number of hops a packet would take if it goes
  // to each of the four possible directions. The smallest number
  // of hops would be the most preferred exit and the route
  // pointing to such direction is returned
  //
  // Four directional distances are calculated first. They tell
  // the number of rows or columns a packet has to traverse when
  // it goes out from each of the four exit interfaces.
  //
  // Then four path lengths, in terms of hops, are calculated.
  // They tells the total number of hops a packet will take
  // if it goes out from each of the four possible exit interfaces.
  // These path lengths are based upon the directional distances
  // mentioned above.
  //
  // Four directional distances are calculated by assuming that a 
  // packet exits from each of the four possible directions. For north
  // going distance to the destination, the distance is either
  //   yLocation - yDest, or 
  //   m_nRows + yLocation - yDest,
  // depending on whether which equlation yields a positive number.
  // As (N+B) MOD N = B MOD N = B if 0 <= B < N, the two equations 
  // above is the same as
  //   (m_nRows + yLocation - yDest) MOD m_nRows.
  // This idea applies to the calculations of the four possible 
  // directions.
  //
  // Four path lengths are
  // - northDist + min (eastDist,  westDist)  for north exit,
  // - eastDist  + min (northDist, southDist) for east  exit,
  // - southDist + min (eastDist,  westDist)  for south exit, and
  // - westDist  + min (northDist, southDist) for west  exit.
  // Note that if the distination for a direction is zero, it means
  // that the local node is on the same row/column as the destination
  // node, and thus that direction is never considered for being an
  // exit interface.
  
  // The number of rows a packet must pass through if it exits the
  // node from the North
  uint32_t northDist = ((m_nRows + m_yLocation) - yDest) % m_nRows;
  NS_LOG_LOGIC ("Northward distance = " << northDist);
  // The number of rows a packet must pass through if it exits the
  // node from the South
  uint32_t southDist = ((m_nRows + yDest) - m_yLocation) % m_nRows;
  NS_LOG_LOGIC ("Southward distance = " << southDist);
  // The number of rows a packet must pass through if it exits the
  // node from the East
  uint32_t eastDist  = ((m_nRows + xDest) - m_xLocation) % m_nRows;
  NS_LOG_LOGIC ("Eastward distance  = " << eastDist);
  // The number of rows a packet must pass through if it exits the
  // node from the West
  uint32_t westDist  = ((m_nRows + m_xLocation) - xDest) % m_nRows;
  NS_LOG_LOGIC ("Westward distance  = " << westDist);
  // The infinity constant for the local use here
  static const uint32_t INF = (uint32_t) - 1;
  // The path length for a packet if it exits from the North of the node.
  // If the local node is on the same row as the destination node, the length
  // is set to inf
  uint32_t northHop = northDist > 0? northDist + min (eastDist,  westDist): INF;
  // The path length for a packet if it exits from the East of the node.
  // If the local node is on the same column as the destination node, the length
  // is set to inf
  uint32_t eastHop  = eastDist > 0?  eastDist  + min (northDist, southDist): INF;
  // The path length for a packet if it exits from the South of the node.
  // If the local node is on the same row as the destination node, the length
  // is set to inf
  uint32_t southHop = southDist > 0? southDist + min (eastDist,  westDist) : INF;
  // The path length for a packet if it exits from the West of the node.
  // If the local node is on the same column as the destination node, the length
  // is set to inf
  uint32_t westHop  = westDist > 0?  westDist  + min (northDist, southDist): INF;
  // Set the following flags to true if the packet should go out
  // from the direction specified. Multiple exits may occur if
  // the distance is the same for such multiple exits.
  //
  // The exit(s) are included if it leads to the shortest path length to
  // the packets' destination, and the exit(s) are excluded if the current
  // node is on the same row/column as the destination node.
  //
  // The minimum path length from the source node to the packets' destination node
  uint32_t minPathLen = min (min (min (northHop, eastHop), southHop), westHop);
  bool goNorth = northHop == minPathLen;
  NS_LOG_LOGIC ("goNorth = " << goNorth << " (" << northHop << " hops)");
  bool goEast  = eastHop == minPathLen && eastDist != 0;
  NS_LOG_LOGIC ("goEast  = " << goEast  << " (" << eastHop  << " hops)");
  bool goSouth = southHop == minPathLen;
  NS_LOG_LOGIC ("goSouth = " << goSouth << " (" << southHop << " hops)");
  bool goWest  = westHop == minPathLen;
  NS_LOG_LOGIC ("goWest  = " << goWest  << " (" << westHop  << " hops)");

  // The route a packet follows
  Ptr<Ipv4Route> returnRoute;

  // let the BmsnPathSelectorTag, added to the packet, to choose
  // an exit direction for the packet if random routing is enabled.
  // Otherwise, use the default priority to choose the exit direction
  // for the packet
  BmsnPathSelectorTag::ExitDirection exitDir;
  if (m_enableRandRouting)
  {
    exitDir = ChooseExitByRandom (p, goNorth, goEast, goSouth, goWest);
    NS_LOG_LOGIC ("Chosen by ChooseExitByRandom the exit interface = " << exitDir);
  }
  else 
  {
    exitDir = ChooseExitByDefault (p, goNorth, goEast, goSouth, goWest);
    NS_LOG_LOGIC ("Chosen by default the exit interface = " << exitDir);
  }
  
  // choose a route according to the exit direction chosen above
  returnRoute = 
    ChooseRouteByExit (exitDir, goNorth, goEast, goSouth, goWest
    );
  NS_LOG_LOGIC ("Chosen by BmsnRouting the exit route and destination = " 
    << returnRoute << "/" << returnRoute->GetSource ()
    );
  // choose a route by the deflection rule defined in the ChooseRouteByDeflection ()
  Ptr<Ipv4Route> deflectRoute = 0;
  // do deflection on packet only if this is enabled
  if (m_enableDeflection)
    deflectRoute = ChooseRouteByDeflection (
      idev, returnRoute, goNorth, goEast, goSouth, goWest, p
      );
  // change the exit route to the one chosen by deflection method
  if (deflectRoute != 0)
  {
    returnRoute = deflectRoute;
    NS_LOG_LOGIC ("Packet exits from interface = " 
      << returnRoute << "/" << returnRoute->GetSource ());
  }

  return returnRoute;
}

int16_t 
BmsnRouting::GetPriority () const
{
  return m_priority;
}

BmsnPathSelectorTag::ExitDirection 
BmsnRouting::ChooseExitByRandom (
  Ptr<Packet> p,
  bool goNorth,
  bool goEast,
  bool goSouth,
  bool goWest
  ) const
{
  NS_LOG_FUNCTION (*p);

  // to store all feasible exits
  typedef vector<BmsnPathSelectorTag::ExitDirection> Vec_t;
  Vec_t feasibleExitsVec;
  if (goNorth) feasibleExitsVec.push_back (BmsnPathSelectorTag::North);
  if (goEast ) feasibleExitsVec.push_back (BmsnPathSelectorTag::East );
  if (goSouth) feasibleExitsVec.push_back (BmsnPathSelectorTag::South);
  if (goWest ) feasibleExitsVec.push_back (BmsnPathSelectorTag::West );
  // pick up an feasible exit randomly
  //
  // get the number of feasible exits first, and
  // generate a random number to pick up one of the
  // feasible exits
  Vec_t::size_type vecSize = feasibleExitsVec.size ();
  UniformVariable rand;
  return feasibleExitsVec.at (rand.GetInteger (0, vecSize-1));
}

BmsnPathSelectorTag::ExitDirection 
BmsnRouting::ChooseExitByDefault (
  Ptr<Packet> p,
  bool goNorth,
  bool goEast,
  bool goSouth,
  bool goWest
  ) const
{
  NS_LOG_FUNCTION (p << goNorth << goEast << goSouth << goWest);

  if (goNorth)
    return BmsnPathSelectorTag::North;
  else if (goEast)
    return BmsnPathSelectorTag::East;
  else if (goSouth)
    return BmsnPathSelectorTag::South;
  else if (goWest)
    return BmsnPathSelectorTag::West;
  else
    return BmsnPathSelectorTag::None;
}

Ptr<Ipv4Route> 
BmsnRouting::ChooseRouteByExit (
  BmsnPathSelectorTag::ExitDirection e,
  bool goNorth,
  bool goEast,
  bool goSouth,
  bool goWest
  ) const
{
  // set only the flag corresponding to "e" if "e" is not None.
  // Othewise, do not alter the four directional flags and let the
  // default behavior, defined below, to choose an exit direction
  // for the packet
  switch (e)
  {
  case BmsnPathSelectorTag::North:  
    goNorth = true;
    goEast  = false;
    goSouth = false;
    goWest  = false;
    break;
  case BmsnPathSelectorTag::East:
    goNorth = false;
    goEast  = true;
    goSouth = false;
    goWest  = false;
    break;
  case BmsnPathSelectorTag::South:
    goNorth = false;
    goEast  = false;
    goSouth = true;
    goWest  = false;
    break;
  case BmsnPathSelectorTag::West:
    goNorth = false;
    goEast  = false;
    goSouth = false;
    goWest  = true;
    break;
  default:
    NS_LOG_WARN ("BmsnPathSelectorTag does not choose an exit direction.");
  };

  // Store the foute to guide the packet to exit the local node.
  // The route is returned to callers
  Ptr<Ipv4Route> returnRoute;
  if (goNorth)      
  {
    returnRoute = m_northRoute;
    NS_LOG_LOGIC ("Decided to go North");
  }
  else if (goEast) 
  {
    returnRoute = m_eastRoute;
    NS_LOG_LOGIC ("Decided to go East");
  }
  else if (goSouth) 
  {
    returnRoute = m_southRoute;
    NS_LOG_LOGIC ("Decided to go South");
  }
  else if (goWest)  
  {
    returnRoute = m_westRoute;
    NS_LOG_LOGIC ("Decided to go West");
  }
  else 
  {
    NS_LOG_LOGIC ("Packet reaches its destination");
    returnRoute = 0;
  }

  return returnRoute;
}

Ptr<Ipv4Route> 
BmsnRouting::ChooseRouteByDeflection (
  Ptr<const NetDevice> idev,
  Ptr<Ipv4Route> exit,
  bool goNorth,
  bool goEast,
  bool goSouth,
  bool goWest,
  Ptr<Packet> p
  )
{
  NS_LOG_FUNCTION (idev << exit << goNorth << goEast << goSouth << goWest << p);

  // obtain the queue profile on the preferred exit direction
  //
  // get the node now the packet is on
  Ptr<Node> localNode = m_ipv4->GetNetDevice (0)->GetNode ();
  // get the route for the most preferred exit direction
  Ptr<Ipv4Route> preferredRoute = exit;
  // get the net device heading the most preferred exit direction
  Ptr<NetDevice> preferredNetDev = preferredRoute->GetOutputDevice ();
  // get the pointer to the queue object in this preferred net device
  PointerValue queueValue;
  preferredNetDev->GetAttribute ("TxQueue", queueValue);
  Ptr<Queue> preferredQueue = queueValue.GetObject ()->GetObject<Queue> ();
  // check if the current packet is going to be dropped
  bool willDrop = preferredQueue->WillDrop (p);
  // return the original exit route as the final route if the packet is not to be dropped
  if (!willDrop)
    return exit;
  // otherwise, choose a route as the final exit route by the deflection rule 
  else
  {
    // get the deflected route
    Ptr<Ipv4Route> deflectedRoute = 
      DoDeflect (idev, exit, goNorth, goEast, goSouth, goWest, p
      );
    // get the current queue size of the deflected exit
    //
    // get the net device first, and than the queue, and finally the queue size
    Ptr<NetDevice> deflectedNetDev = deflectedRoute->GetOutputDevice ();
    deflectedNetDev->GetAttribute ("TxQueue", queueValue);
    Ptr<Queue> deflectedQueue = queueValue.GetObject ()->GetObject<Queue> ();
    // print out debug message
    NS_LOG_DEBUG ("Packet-" 
      << p->GetUid () << " deflected at node (" 
      << GetXLocation () << ", " 
      << GetYLocation () << ")"
      );
    // print out more detail information about this deflection
    NS_LOG_INFO ("Preferred exit = " << preferredRoute->GetSource ());
    NS_LOG_INFO ("Queue size = " << preferredQueue->GetNPackets () << " packets");
    NS_LOG_INFO ("Deflected exit = " << deflectedRoute->GetSource ());
    NS_LOG_INFO ("Queue size = " << deflectedQueue->GetNPackets () << " packets");
    // return the deflection result
    return deflectedRoute;
  }
 
}

Ptr<Ipv4Route>
BmsnRouting::DoDeflect (
  Ptr<const NetDevice> idev,
  Ptr<Ipv4Route> exit,
  bool goNorth,
  bool goEast,
  bool goSouth,
  bool goWest,
  Ptr<Packet> p
  )
{
  NS_LOG_FUNCTION ("idev" << exit << goNorth << goEast << goSouth << goWest << "p");
  // store all routes for that can be used as a delfected route for the current packet
  vector< Ptr<Ipv4Route> > deflectableRoutes;
  // Get the interface indexes of all net devices so as to check if two interfaces are the same
  //
  // get the interface index of the input net device. If the packet is generated locally,
  // there is no input net device. In this case idevIfIndex is set to an impossible value.
  uint32_t idevIfIndex = (uint32_t) -1;
  if (idev != 0)
    idevIfIndex = idev->GetIfIndex ();
  // get the interface index of the preferred exit net device
  uint32_t exitIfIndex = exit->GetOutputDevice ()->GetIfIndex ();
  // get the interface indexes of all the routes facing each of the four directions
  uint32_t northIfIndex = m_northRoute->GetOutputDevice ()->GetIfIndex ();
  uint32_t eastIfIndex  = m_eastRoute->GetOutputDevice  ()->GetIfIndex ();
  uint32_t southIfIndex = m_southRoute->GetOutputDevice ()->GetIfIndex ();
  uint32_t westIfIndex  = m_westRoute->GetOutputDevice  ()->GetIfIndex ();
  // find out if the output interfaces' queue is full
  PointerValue northQueuePV;
  m_northRoute->GetOutputDevice ()->GetAttribute ("TxQueue", northQueuePV);
  bool northFull = northQueuePV.GetObject ()->GetObject<Queue> ()->WillDrop (p);
  NS_LOG_LOGIC ("northFull = " << northFull);
  PointerValue eastQueuePV;
  m_eastRoute->GetOutputDevice  ()->GetAttribute ("TxQueue", eastQueuePV);
  bool eastFull = eastQueuePV.GetObject   ()->GetObject<Queue> ()->WillDrop (p);
  NS_LOG_LOGIC ("eastFull = " << eastFull);
  PointerValue southQueuePV;
  m_southRoute->GetOutputDevice ()->GetAttribute ("TxQueue", southQueuePV);
  bool southFull = southQueuePV.GetObject ()->GetObject<Queue> ()->WillDrop (p);
  NS_LOG_LOGIC ("southFull = " << southFull);
  PointerValue westQueuePV;
  m_westRoute->GetOutputDevice  ()->GetAttribute ("TxQueue", westQueuePV);
  bool westFull = westQueuePV.GetObject   ()->GetObject<Queue> ()->WillDrop (p);
  NS_LOG_LOGIC ("westFull = " << westFull);
  // find out all the deflectable routes. These route are feasible, not "exit", and not "idev"
  //
  // check each of the four directional routes and see if they are deflectable.
  // add the route into the vector if it is deflectable
  if ( !northFull && (northIfIndex != idevIfIndex) && (northIfIndex != exitIfIndex) )
  {
    NS_LOG_LOGIC ("North exit is deflectable");
    deflectableRoutes.push_back (m_northRoute);
  }
  if ( !eastFull &&  (eastIfIndex != idevIfIndex) && (eastIfIndex != exitIfIndex) )
  {
    NS_LOG_LOGIC ("East exit is deflectable");
    deflectableRoutes.push_back (m_eastRoute);
  }
  if ( !southFull &&  (southIfIndex != idevIfIndex) && (southIfIndex != exitIfIndex) )
  {
    NS_LOG_LOGIC ("South exit is deflectable");
    deflectableRoutes.push_back (m_southRoute);
  }
  if ( !westFull &&  (westIfIndex != idevIfIndex) && (westIfIndex != exitIfIndex) )
  {
    NS_LOG_LOGIC ("West exit is deflectable");
    deflectableRoutes.push_back (m_westRoute);
  }
  // Get the number of deflectable routes
  uint8_t nDeflectableRoutes = deflectableRoutes.size ();
  NS_LOG_LOGIC ("Number of deflectable routes = " << (uint32_t) nDeflectableRoutes);
  // start to select one deflectable route
  // 
  // store the final route for deflecting the packet
  Ptr<Ipv4Route> deflectedRoute;
  // determine the deflection route.
  if (!deflectableRoutes.empty ())
    deflectedRoute = deflectableRoutes.at (m_rand.GetInteger (0, nDeflectableRoutes-1));
  // if all interfaces are queue full, forward the packet to its original
  // exit interface, where the queue is also full and let it to drop the packet
  else
  {
    NS_LOG_DEBUG ("All exits are queue full!");
    deflectedRoute = exit;
  }

  NS_LOG_LOGIC ("DeflectedRoute = " << deflectedRoute->GetSource ());
  return deflectedRoute;

  //NS_ASSERT_MSG (false, "No deflection is implemented.");
  //return 0; 
}

Ptr<Ipv4Route> 
BmsnRouting::GetRouteTo (BmsnPathSelectorTag::ExitDirection e) const
{
  switch (e)
  {
  case BmsnPathSelectorTag::East:
    return m_eastRoute; 
    break;
  case BmsnPathSelectorTag::South:
    return m_southRoute; 
    break;
  case BmsnPathSelectorTag::West:
    return m_westRoute; 
    break;
  case BmsnPathSelectorTag::North:
    return m_northRoute; 
    break;
  case BmsnPathSelectorTag::None:
    NS_LOG_WARN ("Null route is return fort the given exit direction = " << e);
    return 0; 
    break;
  default:
    NS_ASSERT_MSG (false, "Found an undefined exit direction!");
    return 0; // never reach here, but this line is to suppress compiler warning
  };
}

/**
 * \todo June 11, 2009 Check why this method is not called upon completion of simulation
 */
void 
BmsnRouting::DoDispose (void)
{
  Ipv4RoutingProtocol::DoDispose ();
}

} // namespace eecityu
} // namespace ns3
